package com.zwj.interview.滑动窗口;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @Author: Zwj
 * @Date: 2022/2/24 16:40
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 *
 * 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: s = "cbaebabacd", p = "abc"
 * 输出: [0,6]
 * 解释:
 * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
 * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 寻找异位词 {

    //找到s中包括t的的全排列
    public List<Integer> findAnagrams(String s, String t) {
        //用于记录字符串T中每个字符出现的次数
        HashMap<Character, Integer> needs = new HashMap<>();
        //用于记录字符串T中每个字符在窗口中出现的次数
        HashMap<Character, Integer> window = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            needs.put(t.charAt(i), needs.getOrDefault(t.charAt(i), 0) + 1);
        }
        int left = 0, right = 0;
        //用来记录有多少个字符满足了条件，如果说valid和needs.size相同，就说明满足了条件
        int valid = 0;
        List<Integer> res=new ArrayList<>();
        while(right<s.length()){
            char c1=s.charAt(right);
            right++;
            //1、不断增加窗口
            if (needs.containsKey(c1)) {
                window.put(c1, window.getOrDefault(c1, 0) + 1);
                if (window.get(c1).equals(needs.get(c1))) {
                    valid++;
                }
            }
            //满足要求的条件就是：right-left==t.length()
            while(right-left>=t.length()){
                if(valid==needs.size()){
                    //结果处理
                    res.add(left);
                }
                char c2 = s.charAt(left);
                left++;
                if (needs.containsKey(c2)) {
                    //这个操作本质就是在缩小窗口，最终维护valid
                   window.put(c2, window.getOrDefault(c2, 0) - 1);
                    if (window.get(c2)<(needs.get(c2))) {
                        valid--;
                    }
                }
            }
        }
        return res;
    }
}